package com.gwcloud.leetcode.tags.array;

import java.util.ArrayList;
import java.util.List;

/** 
* @ClassName   : Leetcode1414 
* @author      : ganwei 
* @date        : 2020年6月15日 
* @Description : 1414. 和为 K 的最少斐波那契数字数目 
*/
public class Leetcode1414 {
    /**
     * -解题思路
     */
	public int findMinFibonacciNumbers(int k) {
        int a = 1, b = 1;
        List<Integer> fl = new ArrayList<Integer>();
        fl.add(a);
        fl.add(b);
        while(a + b <= k) {
        	fl.add(a+b);
        	int c = a + b;
        	a = b;
        	b = c;
        }
        
        int ans = 0;
        for(int i = fl.size() - 1; i >= 0; i--) {
        	if(k >= fl.get(i)) {
        		ans++;
        		k -= fl.get(i);
        	}
        }
        return ans;
    }
    
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	
    }
}
